package com.lw.leetcode.arr.b;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 2537. 统计好子数组的数目
 * b
 * arr
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/15 16:55
 */
public class CountGood {

    public static void main(String[] args) {
        CountGood test = new CountGood();

        // 1
        int[] nums = {1, 1, 1, 1, 1};
        int k = 3;

        // 4
//        int[] nums = {3, 1, 4, 3, 2, 2, 4};
//        int k = 2;

        // 16
//        int[] nums = {1, 1, 3, 1, 2, 1, 2, 2, 1, 2, 1, 2, 3, 3};
//        int k = 14;

        // 4
//        int[] nums = {2, 3, 2, 2, 3, 3, 2, 3, 3, 2};
//        int k = 13;

        long l = test.countGood(nums, k);
        System.out.println(l);
    }

    public long countGood(int[] nums, int k) {
        int st = 0;
        long sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int item = 0;
        for (int num : nums) {
            Integer c = map.getOrDefault(num, 0);
            item += c;
            map.put(num, c + 1);
            while (item >= k) {
                num = nums[st];
                c = map.get(num);
                if (c == 1) {
                    map.remove(num);
                } else {
                    c--;
                    item -= c;
                    map.put(num, c);
                }
                st++;
            }
            sum += st;
        }
        return sum;
    }

}
